home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / deltablu / deltablu.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-17  |  9.9 KB  |  447 lines
  1. /******************************************************************************
  2.  DeltaBlue.c
  3.  
  4.     DeltaBlue incremental constraint solver.
  5.  
  6. *******************************************************************************/
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include "List.h"
  11. #include "Constraints.h"
  12. #include "DeltaBlue.h"
  13.  
  14. /******* Private Macros and Prototypes *******/
  15.  
  16. #define OUT_VAR(c)    (c->variables[c->methodOuts[c->whichMethod]])
  17.  
  18. void        FreeVariable(Variable);
  19. void        AddIfSatisfiedInput(Constraint);
  20. void        CollectSatisfiedInputs(Variable);
  21. List        MakePlan(void);
  22. void        IncrementalAdd(Constraint);
  23. void        AddAtStrength(Constraint);
  24. void        IncrementalRemove(Constraint);
  25. Boolean        AddPropagate(Constraint);
  26. void        CollectUnsatisfied(Constraint);
  27. void        RemovePropagateFrom(Variable);
  28. Constraint    Satisfy(Constraint);
  29. int        ChooseMethod(Constraint);
  30. void        Recalculate(Constraint);
  31. int        OutputWalkStrength(Constraint);
  32. Boolean        ConstantOutput(Constraint);
  33. Boolean        InputsKnown(Constraint);
  34. void        NewMark(void);
  35. void        Error(char *);
  36. Constraint    NextDownstreamConstraint(List, Variable);
  37.  
  38. /******* DeltaBlue Globals *******/
  39.  
  40. List allVariables = NULL;
  41. static long currentMark = 0;
  42. static List hot = NULL;    /* used to collect "hot" constraints */
  43. static List todo1 = NULL; /* used by AddPropagate */
  44. static List todo2 = NULL; /* used by RemovePropagate */
  45.  
  46. /******** Public: Initialization *******/
  47.  
  48. void InitDeltaBlue(void)
  49. {
  50.     Variable v;
  51.  
  52. /*
  53.     if (allVariables == NULL) allVariables = List_Create(128);
  54.     v = (Variable) List_RemoveFirst(allVariables);
  55.     while (v != NULL) {
  56.     FreeVariable(v);
  57.     v = (Variable) List_RemoveFirst(allVariables);
  58.     }
  59.     List_RemoveAll(allVariables);
  60.     currentMark = 0;
  61. */
  62.     allVariables = List_Create(100000);
  63.     hot = List_Create(100000);
  64.     todo1 = List_Create(100000);
  65.     todo2 = List_Create(100000);
  66.     currentMark = 0;
  67. }
  68.  
  69. /* this is used when we know we are going to throw away all variables */
  70. static void FreeVariable(v)
  71. Variable v;
  72. {
  73.     Constraint c;
  74.     int i;
  75.  
  76.     c = (Constraint) List_RemoveFirst(v->constraints);
  77.     while (c != NULL) {
  78.     for (i = c->varCount - 1; i >= 0; i--) {
  79.        List_Remove((c->variables[i])->constraints, (Element) c);
  80.     }
  81.     Constraint_Destroy(c);
  82.     c = (Constraint) List_RemoveFirst(v->constraints);
  83.     }
  84.     Variable_Destroy(v);
  85. }
  86.  
  87. /******** Public: Variables and Constraints *******/
  88.  
  89. void AddVariable(v)
  90. Variable v;
  91. {
  92.     List_Add(allVariables, v);
  93. }
  94.  
  95. void DestroyVariable(v)
  96. Variable v;
  97. {
  98.     Constraint c;
  99.  
  100.     c = (Constraint) List_RemoveFirst(v->constraints);
  101.     while (c != NULL) {
  102.     DestroyConstraint(c);
  103.     c = (Constraint) List_RemoveFirst(v->constraints);
  104.     }
  105.     List_Remove(allVariables, v);
  106.     Variable_Destroy(v);
  107. }
  108.  
  109. void AddConstraint(c)
  110. register Constraint c;
  111. {
  112.     register int i;
  113.  
  114.     for (i = c->varCount - 1; i >= 0; i--) {
  115.     List_Add((c->variables[i])->constraints, (Element) c);
  116.     }
  117.     c->whichMethod = NO_METHOD;
  118.     IncrementalAdd(c);
  119. }
  120.  
  121. void DestroyConstraint(c)
  122. register Constraint c;
  123. {
  124.     register int i;
  125.  
  126.     if (SATISFIED(c)) IncrementalRemove(c);
  127.     for (i = c->varCount - 1; i >= 0; i--) {
  128.     List_Remove((c->variables[i])->constraints, (Element) c);
  129.     }
  130.     Constraint_Destroy(c);
  131. }
  132.  
  133. /******** Public: Plan Extraction *******/
  134.  
  135. static void AddIfSatisfiedInput(c)
  136. Constraint c;
  137. {
  138.     if (c->inputFlag && SATISFIED(c)) {
  139.     List_Add(hot, c);
  140.     }
  141. }
  142.  
  143. static void CollectSatisfiedInputs(v)
  144. Variable v;
  145. {
  146.     List_Do(v->constraints, AddIfSatisfiedInput);
  147. }
  148.  
  149. List ExtractPlan(void)
  150. {
  151.     if (hot == NULL) hot = List_Create(128);
  152.     List_RemoveAll(hot);
  153.     List_Do(allVariables, CollectSatisfiedInputs);
  154.     return MakePlan();
  155. }
  156.  
  157. List ExtractPlanFromConstraint(c)
  158. Constraint c;
  159. {
  160.     if (hot == NULL) hot = List_Create(128);
  161.     List_RemoveAll(hot);
  162.     AddIfSatisfiedInput(c);
  163.     return MakePlan();
  164. }
  165.  
  166. List ExtractPlanFromConstraints(constraints)
  167. List constraints;
  168. {
  169.     if (hot == NULL) hot = List_Create(128);
  170.     List_RemoveAll(hot);
  171.     List_Do(constraints, AddIfSatisfiedInput);
  172.     return MakePlan();
  173. }
  174.  
  175. /******* Private: Plan Extraction *******/
  176.  
  177. static List MakePlan()
  178. {
  179.     register List    plan;
  180.     register Constraint    nextC;
  181.     register Variable    out;
  182.  
  183.     NewMark();
  184.     plan = List_Create(50000);
  185.     nextC = (Constraint) List_RemoveFirst(hot);
  186.     while (nextC != NULL) {
  187.     out = OUT_VAR(nextC);
  188.     if ((out->mark != currentMark) && InputsKnown(nextC)) {
  189.         List_Add(plan, nextC);
  190.         out->mark = currentMark;
  191.         nextC = NextDownstreamConstraint(hot, out);
  192.     } else {
  193.         nextC = (Constraint) List_RemoveFirst(hot);
  194.     }
  195.     }
  196.     return plan;
  197. }
  198.  
  199. static Boolean InputsKnown(c)
  200. register Constraint c;
  201. {
  202.     register int    outIndex, i;
  203.     register Variable    in;
  204.  
  205.     outIndex = c->methodOuts[c->whichMethod];
  206.     for (i = c->varCount - 1; i >= 0; i--) {
  207.     if (i != outIndex) {
  208.         in = c->variables[i];
  209.         if ((in->mark != currentMark) &&
  210.             (!in->stay) &&
  211.         (in->determinedBy != NULL)) {
  212.             return false;
  213.         }
  214.     }
  215.     }
  216.     return true;
  217. }
  218.  
  219. /******* Private: Adding *******/
  220.  
  221. static void IncrementalAdd(c)
  222. Constraint c;
  223. {
  224.     register Constraint overridden;
  225.  
  226.     NewMark();
  227.     overridden = Satisfy(c);
  228.     while (overridden != NULL) {
  229.     overridden = Satisfy(overridden);
  230.     }
  231. }
  232.  
  233. static Constraint Satisfy(c)
  234. register Constraint c;
  235. {
  236.     register int    outIndex, i;
  237.     register Constraint    overridden;
  238.     register Variable    out;
  239.  
  240.     c->whichMethod = ChooseMethod(c);
  241.     if (SATISFIED(c)) {
  242.     /* mark inputs to allow cycle detection in AddPropagate */
  243.     outIndex = c->methodOuts[c->whichMethod];
  244.     for (i = c->varCount - 1; i >= 0; i--) {
  245.         if (i != outIndex) {
  246.         c->variables[i]->mark = currentMark;
  247.         }
  248.     }
  249.     out = c->variables[outIndex];
  250.     overridden = (Constraint) out->determinedBy;
  251.     if (overridden != NULL) overridden->whichMethod = NO_METHOD;
  252.     out->determinedBy = c;
  253.     if (!AddPropagate(c)) {
  254.         Error("Cycle encountered");
  255.         return NULL;
  256.     }
  257.     out->mark = currentMark;
  258.     return overridden;
  259.     } else {
  260.     if (c->strength == S_required) {
  261.         Error("Could not satisfy a required constraint");
  262.     }
  263.     return NULL;
  264.     }
  265. }
  266.  
  267. static int ChooseMethod(c)
  268. register Constraint c;
  269. {
  270.     register int    best, bestOutStrength, m;
  271.     register Variable    mOut;
  272.  
  273.     best = NO_METHOD;
  274.     bestOutStrength = c->strength;
  275.     for (m = c->methodCount - 1; m >= 0; m--) {
  276.     mOut = c->variables[c->methodOuts[m]];
  277.     if ((mOut->mark != currentMark) &&
  278.          (Weaker(mOut->walkStrength, bestOutStrength))) {
  279.         best = m;
  280.         bestOutStrength = mOut->walkStrength;
  281.     }
  282.     }
  283.     return best;
  284. }
  285.  
  286. static Boolean AddPropagate(c)
  287. register Constraint c;
  288. {
  289.     register Constraint    nextC;
  290.     register Variable    out;
  291.  
  292.     List_RemoveAll(todo1);
  293.     nextC = c;
  294.     while (nextC != NULL) {
  295.     out = OUT_VAR(nextC);
  296.     if (out->mark == currentMark) {
  297.         /* remove the cycle-causing constraint */
  298.         IncrementalRemove(c);
  299.         return false;
  300.     }
  301.     Recalculate(nextC);
  302.     nextC = NextDownstreamConstraint(todo1, out);
  303.     }
  304.     return true;
  305. }
  306.  
  307. /******* Private: Removing *******/
  308.  
  309. static List unsatisfied;    /* used to collect unsatisfied downstream constraints */
  310. static int strength;        /* used to add unsatisfied constraints in strength order */
  311.  
  312. static void AddAtStrength(c)
  313. register Constraint c;
  314. {
  315.     if (c->strength == strength) IncrementalAdd(c);
  316. }
  317.  
  318. static void CollectUnsatisfied(c)
  319. Constraint c;
  320. {
  321.     if (!SATISFIED(c)) List_Add(unsatisfied, c);
  322. }
  323.  
  324. void IncrementalRemove(c)
  325. Constraint c;
  326. {
  327.     Variable out;
  328.     register int i;
  329.  
  330.     out = OUT_VAR(c);
  331.     c->whichMethod = NO_METHOD;
  332.     for (i = c->varCount - 1; i >= 0; i--) {
  333.     List_Remove((c->variables[i])->constraints, (Element) c);
  334.     }
  335.     unsatisfied = List_Create(8);
  336.     RemovePropagateFrom(out);
  337.     for (strength = S_required; strength <= S_weakest; strength++) {
  338.     List_Do(unsatisfied, AddAtStrength);
  339.     }
  340.     List_Destroy(unsatisfied);
  341. }
  342.  
  343. static void RemovePropagateFrom(v)
  344. register Variable v;
  345. {
  346.     register Constraint    nextC;
  347.  
  348.     List_RemoveAll(todo2);
  349.     v->determinedBy = NULL;
  350.     v->walkStrength = S_weakest;
  351.     v->stay = true;
  352.     while (true) {
  353.     List_Do(v->constraints, CollectUnsatisfied);
  354.     nextC = NextDownstreamConstraint(todo2, v);
  355.     if (nextC == NULL) {
  356.         break;
  357.     } else {
  358.         Recalculate(nextC);
  359.         v = OUT_VAR(nextC);
  360.     }
  361.     }
  362. }
  363.  
  364. /******* Private: Recalculation *******/
  365.  
  366. static void Recalculate(c)
  367. register Constraint c;
  368. {
  369.     register Variable out;
  370.  
  371.     out = OUT_VAR(c);
  372.     out->walkStrength = OutputWalkStrength(c);
  373.     out->stay = ConstantOutput(c);
  374.     if (out->stay) c->execute(c);
  375. }
  376.  
  377. static int OutputWalkStrength(c)
  378. register Constraint c;
  379. {
  380.     register int outIndex, minStrength, m, mOutIndex;
  381.  
  382.     minStrength = c->strength;
  383.     outIndex = c->methodOuts[c->whichMethod];
  384.     for (m = c->methodCount - 1; m >= 0; m--) {
  385.         mOutIndex = c->methodOuts[m];
  386.     if ((mOutIndex != outIndex) &&
  387.         (Weaker(c->variables[mOutIndex]->walkStrength, minStrength))) {
  388.         minStrength = c->variables[mOutIndex]->walkStrength;
  389.     }
  390.     }
  391.     return minStrength;
  392. }
  393.  
  394. static Boolean ConstantOutput(c)
  395. register Constraint c;
  396. {
  397.     register int outIndex, i;
  398.  
  399.     if (c->inputFlag) return false;
  400.     outIndex = c->methodOuts[c->whichMethod];
  401.     for (i = c->varCount - 1; i >= 0; i--) {
  402.     if (i != outIndex) {
  403.         if (!c->variables[i]->stay) return false;
  404.     }
  405.     }
  406.     return true;
  407. }
  408.  
  409. /******* Private: Miscellaneous *******/
  410.  
  411. static void Error(s)
  412. char *s;
  413. {
  414.     printf("DeltaBlue.c error: %s.\n", s);
  415.     exit(-1);
  416. }
  417.  
  418. static void NewMark(void)
  419. {
  420.     currentMark++; 
  421. }
  422.  
  423. static Constraint NextDownstreamConstraint(todo, variable)
  424. List todo;
  425. Variable variable;
  426. {
  427.     List allC = variable->constraints;
  428.     register Constraint *nextPtr = (Constraint *) &(allC->slots[allC->first]);
  429.     register Constraint *lastPtr = (Constraint *) &(allC->slots[allC->last]);
  430.     register Constraint determiningC = variable->determinedBy;
  431.     Constraint first = NULL;
  432.  
  433.     for ( ; nextPtr <= lastPtr; nextPtr++) {
  434.         if ((*nextPtr != determiningC) && SATISFIED(*nextPtr)) {
  435.             if (first == NULL) {
  436.         first = *nextPtr;
  437.             } else {
  438.         List_Add(todo, *nextPtr);
  439.             }
  440.     }
  441.     }
  442.     if (first == NULL) {
  443.         first = (Constraint) List_RemoveFirst(todo);
  444.     }
  445.     return first;
  446. }
  447.